Parametric signal processing is used in many areas such as speech and image analysis, synthesis and recognition, neurophysics, geophysics, array processing, computerized tomography, communications and astronomy, to name but a few.
One example of signal processing of particular importance is the linear prediction technique which may be used for spectral estimation, and in particular for speech analysis, synthesis and recognition and for the processing of seismic signals, to enable the reconstruction of geophysical substrata. The linear prediction technique employs a specialized autocorrelation function.
Another form of signal processing which finds a multitude of applications, is the determination of an optimal (in the least square sense) finite impulse response (FIR) filter. A signal processor employing such a technique works with the autocorrelation of the filter input signal and the cross-correlation between the input and the desired response signal, and may be used in many of the above-mentioned applications.
Still another form of signal processing of particular importance is known in the art as "L-step ahead" prediction and filtering, for solving the "optimum lag" problem. This technique is especially useful in designing spiking and shaping filters. Signal processors which perform this function employ a specialized autocorrelation function which also takes into account a time lag associated with the system.
Generally, as the order of the system under investigation increases, the complexity of the signal processing necessary to provide useful information also increases. For example, using the general Gaussian elimination procedure, a system of order p can be processed in "O(p.sup.3)" steps, indicating the number of steps as being "on the order of" p.sup.3, i.e., a function of p cubed. Thus, it will be appreciated that a system having order of p=100 requires on the order of one million processing steps to process the signal, a limitation of readily apparent significance, especially where real time processing is required.
Signal processing techniques have been developed which have reduced the number of operations required to process a signal. One such method has been based on a technique developed by N. Levinson, which requires O(p.sup.2) sequential operations to process the signal. In particular, the "Levinson technique" requires O(2.p.sup.2) sequential operations in order to process the signal. A version of this technique, known as the "Levinson-Durbin" technique, which is specialized for the linear prediction problem, requires O(1.p.sup.2) sequential operations to process the signal. Neither of these schemes is suitable for parallel implementation. On the general subject of the Levinson and Levinson-Durbin techniques, see N. Levinson, "The Wiener RMS (Root-Mean-Square) Error Criterion in Filter Design and Prediction", J. Math Phys., Vol. 25, pages 261-278, January 1947; and J. Durbin, "The Filtering of Time Series Models", Rev, Int. Statist. Inst., Vol. 28, pages 233-244, 1960.
Although they represent an order of magnitude improvement over the Gaussian elimination technique, the Levinson and Levinson-Durbin techniques are too slow for many complex systems where real time processing is required.
Another way of implementing the main recursion of the Levinson-Durbin technique, for the computation of what is widely known as "lattice coefficients", was developed by Schur in 1917, in order to establish a system stability criterion. See I. Schur, "Uber Potenzreihen Die In Innern Des Einheitskreises Beschrankt Sind", J. Reine Angewandte Mathematik, Vol. 147, 1917, pages 205-232. Lev-Ari and Kailath, of Stanford University, have developed a different approach, based on the Schur and Levinson techniques, which provides a triangular "ladder" structure for signal processing. The Lev-Ari and Kailath technique uses the signal, per se, as the input to the processor, rather than autocorrelation coefficients, and it is used in the signal modelling context. See H. Lev-Ari and T. Kailath, "Schur and Levinson Algorithms for Non-Stationary Processes", IEEE International Conference on Acoustics, Speech and Signal Processing, 1981, pages 860-864.
In another modification to the Schur technique, Le Roux and C. Gueguen rederived the Schur algorithm, giving emphasis to the finite word length implementation, using fixed point arithmetics. See Le Roux and Gueguen, "A Fixed Point Computation of Partial Correlation, Coefficients", IEEE Transactions on Acoustics, Speech, and Signal Processing, June 1977, pages 257-259.
Finally, Kung and Hu, have developed a parallel scheme, based on the Schur technique, which uses a plurality of parallel processors, to process a signal, having order p, in O(p) operations, a significant improvement compared to the Levinson-Durbin technique. See Kung and Hu, "A Highly Concurrent Algorithm and Pipelined Architecture for Solving Toeplitz Systems", IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-31, No. 1, February 1983, pp. 66-76. However, the application of the Kung and Hu technique is severely limited insofar as it requires that the number of processors be equal to the order of the system to be solved. Thus, the Kung and Hu technique cannot process a signal produced by a system having an order greater than the number of parallel processors. System complexity is therefore a major limiting factor in using the Kung and Hu technique, insofar as many complex systems may have orders much higher than the number of parallel processors currently available in modern VLSI or other technology.
The co-pending patent applications, identified above, overcome the difficulties associated with the prior art signal processors and methods by providing optimal techniques for obtaining lattice predictor coefficients (in Ser. Nos. 837,260 and 904,382), for obtaining lattice filter coefficients, for LS-FIR filtering (in Ser. No. 021,256), and for obtaining direct predictor and filter coefficients, for linear prediction and LS-FIR filtering (in Ser. No. 084,929).
The techniques employed in the co-pending applications use "superlattice" and "superladder" structures to implement the recursions disclosed in the applications. These superlattice and superladder structures are "two-order" structures, meaning that the basic computational elements of such structures produce intermediate and final filter, or predictor, values, e.g., of order m+1, by processing only values having order m. For example, FIG. 1 herein, which is based on FIG. 3 of co-pending application Ser. Nos. 837,260 and 904,382, illustrate that the intermediate and final values of .zeta..sub.i.sup.m, having orders m are produced from intermediate values of .zeta..sub.i.sup.m-1, having order m-1.
Specifically, a system signal is applied to a digital autocorrelator 10, FIG. 1, which produces autocorrelation coefficients r.sub.0 through r.sub.8, which characterize the system. The coefficients are applied to an input device 12, such as a digital register or memory. Each autocorrelation coefficient, except for the first, r.sub.0, and the last, r.sub.8, is multiplied by a first lattice predictor coefficient k.sub.1, which is produced from r.sub.0 and r.sub.1 (.zeta..sub.0.sup.0 and .zeta..sub.1.sup.0), according to the general formula: EQU k.sub.p =-.zeta..sub.p.sup.p-1 /.zeta..sub.0.sup.p-1
The product of each such multiplication is added, individually, to the adjacent two autocorrelation coefficients, to produce the first intermediate values .zeta..sub.n.sup.1, where n=0, 2 through 8 and -1 to -6. For example, autocorrelation coefficient r.sub.3, designated as .zeta..sub.3.sup.0 and .zeta..sub.-3.sup.0, for the sake of conformance with the intermediate variables, is multiplied by lattice predictor coefficient k.sub.1 in multipliers 14 and 16, respectively, and autocorrelation coefficients r.sub.2 and r.sub.4 are added, individually, to each product, in adders 18 and 20, respectively, to produce a pair of first intermediate values .zeta..sub.-2.sup.1 and .zeta..sub.4.sup.1, respectively. Similarly, another two first intermediate values, e.g., .zeta..sub.-1.sup.1 and .zeta..sub.3.sup.1, are produced by multiplying autocorrelation coefficient r.sub.2 by the lattice predictor coefficient k.sub.1, and adding, individually, the adjacent autocorrelation coefficients, r.sub.1 and r.sub.3 to the products.
The second intermediate values are derived from the first intermediate values in a similar manner. First, k.sub.2 is derived from the ratio of .zeta..sub.2.sup.1 and .zeta..sub.0.sup.1 in accordance with the formula given above. Then, second intermediate values .zeta..sub.3.sup.2 and .zeta..sub.0.sup.2, for example, are produced by multiplying the first intermediate values .zeta..sub.-1.sup.1 and .zeta..sub.2.sup.1 by the lattice predictor coefficient k.sub.2, and adding the adjacent first intermediate values .zeta..sub.3.sup.1 and .zeta..sub.0.sup.1 to the products, individually. The signal processing continues according to the basic lattice recursion disclosed in Ser. Nos. 837,260 and 904,382, until the final values .zeta..sub.8.sup.7 and .zeta..sub.0.sup.7 are obtained, from which the last lattice predictor coefficient k.sub.8 can be produced.
The lattice predictor coefficients k.sub.i completely characterize the linear predictor and can be used instead of the direct predictor coefficients a.sub.i. They are many times preferred for storage, transmission and fast speech synthesis, since they have the advantages of being ordered, bounded by unity and can readily be used for stability control, efficient quantization, and the like. Since r.sub.0 corresponds to the energy of the signal, and will therefore have the greatest amplitude of any of the signals processed by the superlattice, all variables can be normalized with respect to r.sub.0, thus facilitating the use of fixed point processing, with its advantages of precision, speed and processing simplicity.
FIG. 2 illustrates a butterfly basic cell from which the superlattice of FIG. 1 can be constructed, as disclosed in co-pending application Ser. No. 837,260. As taught by that co-pending application, the superlattice structure of FIG. 1 can be implemented by the repeated use of such butterfly basic cells, in the manner illustrated in FIG. 3. The reference numerals used in FIG. 2 correspond to those of FIG. 1.
Referring to FIG. 2, it will be appreciated that the multiplication of r.sub.3 by k.sub.1 is performed twice, in multipliers 14 and 16. This double operation can be eliminated by employing a single multiplier 16' in a "reduced basic cell", illustrated in FIG. 4. In this case, the multiplier 16' provides two outputs, one of which is added to r.sub.2 in adder 18, to provide the intermediate quantity .zeta..sub.-2.sup.1, and a second output which is added to r.sub.4 in adder 20, to produce intermediate value .zeta..sub.4.sup.1. This hardware reduction, however, can only be achieved for those basic cells used to produce the first intermediate values, since all succeeding basic cells receive at their inputs four distinct quantities.